// 28. [kmp] 实现 strStr()
// https://leetcode.cn/problems/implement-strstr/
// 实现strStr()函数。
// 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle
// 字符串出现的第一个位置下标从 0 开始。如果不存在，则返回 -1 。
// 对于本题而言，当needle是空字符串时我们应当返回 0
// 这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
// 输入：haystack = "hello", needle = "ll"
// 输出：2
// 输入：haystack = "aaaaa", needle = "bba"
// 输出：-1
// 提示：1 <= haystack.length, needle.length <= 104, haystack 和 needle
// 仅由小写英文字符组成 Knuth-Morris-Pratt 算法 算法的核心为前缀函数，记作
// π(i)，其定义如下： 对于长度为 mm 的字符串 ss，其前缀函数 π(i)(0≤i<m) 表示 s
// 的子串 s[0:i] 的最长的相等的真前缀与真后缀的长度。
// 特别地如果不存在符合条件的前后缀，那么 π(i)=0。
// 其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。
// 我们举个例子说明：字符串 aabaaabaabaaab 的前缀函数值依次为
//  0,1,0,1,2,2,30,1,0,1,2,2,3。
// 对于任意字符串 π(0)=0
// π(0)=0，因为 aa 没有真前缀和真后缀，根据规定为 0
// π(1)=1，因为 aa 最长的一对相等的真前后缀为 aa，长度为 11；
// π(2)=0，因为 aab 没有对应真前缀和真后缀，根据规定为 0
// π(3)=1，因为 aaba 最长的一对相等的真前后缀为 a，长度为 1
// π(4)=2，因为 aabaa 最长的一对相等的真前后缀为 aa，长度为 2
// π(5)=2，因为 aabaaa 最长的一对相等的真前后缀为 aa，长度为 2
// π(6)=3，因为 aabaaab 最长的一对相等的真前后缀为 aab，长度为 3
// 时间复杂度O(n+m)，其中 n字符串haystack 的长度，m 是字符串 needle 的长度。
class Solution {
 public:
  int strStr(string haystack, string needle) {
    int n = haystack.size(), m = needle.size();
    if (m == 0) {
      return 0;
    }
    vector<int> pi(m);
    for (int i = 1, j = 0; i < m; i++) {
      while (j > 0 && needle[i] != needle[j]) {
        j = pi[j - 1];
      }
      if (needle[i] == needle[j]) {
        j++;
      }
      pi[i] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
      while (j > 0 && haystack[i] != needle[j]) {
        j = pi[j - 1];
      }
      if (haystack[i] == needle[j]) {
        j++;
      }
      if (j == m) {
        return i - m + 1;
      }
    }
    return -1;
  }
};